package leetcode.每日一题;


import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/6/19 16:21
 * @description：https://leetcode-cn.com/problems/eight-queens-lcci/
 */
public class 八皇后 {

    @Test
    public void test() {
        Solution solution = new Solution();
        List<List<String>> lists = solution.solveNQueens(8);
        for (List<String> list : lists) {
            System.out.println(list);
        }
    }


    class Solution {
        int max;
        List<List<String>> ans = new ArrayList<>();
        int[] array;

        public List<List<String>> solveNQueens(int n) {
            max = n;
            array = new int[max];
            check(0);
            return ans;
        }

        public void check(int n) {
            if (n == max) {
                List<String> sub = generateList(array);
                ans.add(new ArrayList<>(sub));
                return;
            }
            for (int i = 0; i < max; i++) {
                array[n] = i;
                if (judge(n)) {
                    check(n + 1);
                }
            }
        }

        private boolean judge(int n) {
            for (int i = 0; i < n; i++) {
                //array[i] == array[n]  不在同一列
                //Math.abs(array[n] - array[i]) == Math.abs(n - i)  不在同一斜线
                if (array[i] == array[n] || Math.abs(array[n] - array[i]) == Math.abs(n - i)) {
                    return false;
                }
            }
            return true;
        }

        public List<String> generateList(int[] nums) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < max; i++) {
                builder.append(".");
            }
            List<String> sub = new ArrayList<>();
            for (int num : nums) {
                StringBuilder builder1 = new StringBuilder(builder);
                builder1.replace(num, num + 1, "Q");
                sub.add(builder1.toString());
            }
            return sub;
        }
    }
}
